\section{Problema 3}

\subsection{Enunciado}
En el pa\'is Exacto, las elecciones son llevadas a cabo mediante eliminaci\'on directa. Cada semana dos candidatos son
seleccionados y enfrentados en votaci\'on popular. El perdedor es eliminado y el ganador, vuelve al conjunto de candidatos
que siguen en carrera. Este proceso se contin\'ua hasta que queda s\'olo un candidato. \\

Para empeorar un poco las cosas, una sola persona tiene que seleccionar a los candidatos a enfrentarse cada semana.
Esta persona resultan ser ustedes! Como son buenos comerciantes, tienen el plan de seleccionar los candidatos de manera
que el candidato de ustedes gane. Tienen adem\'as acceso a datos de inteligencia que permiten inferir qu\'e candidato
ganar\'a en cada posible enfrentamiento entre candidatos. Luego, es posible generar un cronograma de enfrentamientos para
que tu candidato gane? \\

Analizar la complejidad temporal usando el modelo uniforme y expresarla en funci\'on de $n$, $m$ y $c$.
Se debe encontrar un algoritmo con complejidad menor o igual que $O(n^{2} * m^{2} )$.

\subsection{Modelado}
Para modelar el problema se usara un grafo dirigido donde los nodos representan a los candidatos que participan de la elección
y una arista desde un nodo $i$ hacia un nodo $j$ representara que el candidato $i$ le gana al candidato $j$ en un enfrentamiento. \\

Si en el problema original se encuentra una solución, es decir una combinación de enfrentamientos que hacen que el candidato que
se quiere favorecer gane, entonces en nuestro modelo se podrá llegar a cualquier otro nodo del grafo desde dicho candidato a través
de un camino dirigido. Esto se debe a que en nuestro grafo una arista desde un nodo $i$ hacia un nodo $j$ representa que $i$ le gana
a $j$ en un enfrentamiento, por lo tanto un camino dirigido desde un nodo hacia otro indica que existe una secuencia de enfrentamientos
tales que al finalizar solo quede el nodo inicial del camino y todos los demás sean eliminados. \\


Si en el grafo que modela el problema encontramos un camino dirigido desde el nodo que representa al candidato a favorecer hacia
todos los demás entonces el problema original tiene solución ya que bastaría con enfrentar a todos los candidatos de a pares en
el orden inverso al que aparecen en cada camino hasta llegar al candidato que se quiere que gane. Esto se debe a que en el modelo
una arista desde un nodo $i$ hacia un nodo $j$ representa que $i$ le gana a $j$ en un enfrentamiento entonces al enfrentar a los
candidatos de a pares en orden inverso al que aparecen en el camino se iría eliminando siempre al último candidato del camino quedandonos
al final sólo con el nodo inicial. Por lo tanto si desde el candidato a favorecer se puede llegar a todos los demás candidatos a través
de algún camino dirigido entonces se podrá generar una secuencia de enfrentamientos tales que al final sólo quede nuestro candidato.

\subsection{Correctitud}
Para construir el grafo que modela el problema primero establecemos a todos los candidatos como sus nodos y luego enfrentamos a todos
los candidatos de a pares y agregamos una arista desde el candidato que haya obtenido una mayor cantidad de votos hacia el otro. En el
caso de haber un empate no se agrega ninguna arista pues ninguno de los candidatos gana ni pierde. \\

Si por ejemplo la entrada estuviera compuesta de $5$ candidatos, $4$ votantes y los siguientes votos: \\

\begin{center}
	\begin{tabular}{ c c c c c c }
	\textbf{Votante 1:} & 1 & 2 & 3 & 4 & 5 \\
	\textbf{Votante 2:} & 2 & 3 & 1 & 4 & 5 \\
	\textbf{Votante 3:} & 3 & 4 & 5 & 1 & 2 \\
	\textbf{Votante 4:} & 5 & 3 & 4 & 1 & 2 \\
	\end{tabular}
\end{center}

Al enfrentar al candidato $1$ con el $2$ gana el candidato $1$ pues obtiene una mayor cantidad de votos (3 votos de los votantes
$1$, $3$ y $4$  contra 1 voto del votante $2$) y por lo tanto se agrega una arista desde el nodo $1$ hacia el nodo $2$ en
el grafo que modela el problema. Luego si enfrentamos el candidato $1$ con el $3$ gana el $3$ (3 votos contra 1) y por lo tanto
agregamos una arista desde el nodo $3$ hacia el $1$. De esta manera continuamos enfrentando a los candidatos de a pares hasta que
se hayan enfrentado todos y al finalizar nos queda el siguiente grafo:

\begin{center}
\begin{tikzpicture}
	\SetVertexNormal[Shape = circle,
                   FillColor  = white]
	%\SetVertexNoLabel
	\SetUpEdge[lw         = 1pt,
					color      = black,
					labelcolor = white,
					labeltext  = black,
					labelstyle = {sloped,draw,text=black}]
					
	\Vertex[x=1, y=3]{1}
	\Vertex[x=0, y=1]{2}
	\Vertex[x=2, y=2]{3}
	\Vertex[x=1, y=0]{4}
	\Vertex[x=3, y=0]{5}
	
	\tikzstyle{EdgeStyle}=[post, bend right]
	\Edges(1,2)
	\Edges(3,1)
	\Edges(3,4)
	\Edges(4,5)
	
	\tikzstyle{EdgeStyle}=[post, bend left]
	\Edges(3,5)
\end{tikzpicture}
\end{center}


Luego una vez armado el grafo, para determinar si el candidato que se quiere favorecer puede ganar la elección es neceario verificar
que desde \'el se pueda llegar a todos los dem\'as candidatos a trav\'es de algun camino dirigido. Si esto es posible entonces
bastar\'ia con enfrentar los candidatos en orden inverso al que se encuentran en el camino e ir eliminando al que pierde (que es
siempre el \'ultimo nodo del camino ya que sabemos que en el grafo una arista desde un nodo $i$ a un nodo $j$ representa que el 
candidato $i$ le gana al candidato $j$). Luego si al terminar de recorrer en orden inverso todos los caminos nos quedamos s\'olo
con el nodo que representa al candidato que estamos favoreciendo entonces este es el ganador. Si en cambio al finalizar el algoritmo
el grafo tiene m\'as nodos que el candidato que queremos favorecer significa que no era posible que dicho candidato ganase. \\

Siguiendo con el ejemplo anterior, en el siguiente gráfico podemos ver que si el candidato al que estamos favoreciendo es el n\'umero 3
entonces el ejercicio encuentra una soluci\'on ya que desde \'este nodo se puede llegar hasta todos los dem\'as a trav\'es de algun camino
dirigido.

\begin{center}
\begin{tikzpicture}
	\SetVertexNormal[Shape = circle,
                   FillColor  = white]
	%\SetVertexNoLabel
	\SetUpEdge[lw         = 1pt,
					color      = black,
					labelcolor = white,
					labeltext  = black,
					labelstyle = {sloped,draw,text=black}]
					
	\Vertex[x=1, y=3]{1}
	\Vertex[x=0, y=1]{2}
	\Vertex[x=1, y=0]{4}
	\Vertex[x=3, y=0]{5}
	
	\tikzstyle{VertexStyle}=[circle, fill=red!20]
	\Vertex[x=2, y=2]{3}
	
	\tikzstyle{EdgeStyle}=[post, bend right, color=red]
	\Edges(1,2)
	\Edges(3,1)
	\Edges(3,4)
	\Edges(4,5)
	
	\tikzstyle{EdgeStyle}=[post, bend left]
	\Edges(3,5)
\end{tikzpicture}
\end{center}

Por lo tanto solo bastar\'ia con realizar los enfretamientos entre los pares de nodos de los caminos
en el orden inverso al que se encuentran en \'este en este para que el candidato 3 gane.
Viendolo con un poco mas de detalle tenemos: \\
\begin{itemize}
	\item \textbf{camino 1}: $3 \rightarrow 1 \rightarrow 2$ ($3$ le gana a $1$ que le gana a $2$).
	\item \textbf{camino 2}: $3 \rightarrow 4 \rightarrow 5$ ($3$ le gana a $4$ que le gana a $5$).
\end{itemize}

Ahora como se puede ver solo basta con enfrentar a cada par de candidatos en el orden inverso al que están en el camino
e ir eliminando el nodo perdedor para que al final s\'olo quede el nodo 3.

\subsection{Pseudoc\'odigo}

\begin{algorithm}[H]
\caption{armarEleccion(Entero $votantes$, Entero $candidatos$, Matriz $votaciones$)}
\begin{algorithmic}[1]
	\STATE $prioridades$ $\leftarrow$ Matriz($votantes * candidatos$);
	\STATE 
	\FOR{$i$ de 1 a $votantes$}
		\FOR{$j$ de 1 a $candidatos$}
			\STATE prioridades[$i$][$votaciones$[$j$]] $\leftarrow$ $j$;
		\ENDFOR
	\ENDFOR
	\STATE
	\RETURN $prioridades$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[H]
\caption{armarGrafo(Entero $votantes$, Entero $candidatos$, Matriz $prioridades$)}
\begin{algorithmic}[1]
	\STATE $grafo$ $\leftarrow$ Digrafo($votantes$)
	\STATE
	\FOR{$i$ de 1 a $candidatos$}
		\FOR{$j$ de $i$ a $candidatos$}
			\STATE $resultado \leftarrow 0$
			\STATE
			\FOR{$v$ de 1 a $votantes$}
				\IF{$prioridades$[$v$][$i$] $<$ $prioridades$[$v$][$j$]}
					\STATE $resultado++$
				\ELSE
					\IF{$prioridades$[$v$][$i$] $>$ $prioridades$[$v$][$j$]}
						\STATE $resultado--$
					\ENDIF
				\ENDIF
			\ENDFOR
			\STATE
			\IF{$resultado > 0$}
				\STATE ponerArista($grafo$, $i$, $j$)
			\ELSE
				\IF{$resultado < 0$}
					\STATE ponerArista($grafo$, $j$, $i$)
				\ENDIF
			\ENDIF
			\STATE
		\ENDFOR
	\ENDFOR
	\STATE
	\RETURN $grafo$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[H]
\caption{recorrerGrafo(Entero $votantes$, Entero $candidatos$, Entero $candidato$, Grafo $grafo$)}
\begin{algorithmic}[1]
	\STATE $visitados$ $\leftarrow$ Vector(nodos($grafo$))
	\STATE $nodos\_por\_recorrer$ $\leftarrow$ Pila
	\STATE
	\STATE $visitados$[$candidato$] $\leftarrow$ \TRUE
	\STATE apilar($nodos\_por\_recorrer$, vecinos($candidato$))
	\STATE
	\WHILE{$\neg$vac\'ia($nodos\_por\_recorrer$)}
		\STATE Entero $nodo$ $\leftarrow$ cima($nodos\_por\_recorrer$)
		\STATE
		\IF{$\neg visitados$[$nodo$]}
			\STATE $visitados$[$nodo$] $\leftarrow$ \TRUE
			\STATE apilar($nodos\_por\_recorrer$, vecinos($nodo$))
		\ENDIF
	\ENDWHILE
	\STATE 
	\IF{todosUno($visitados$)}
		\RETURN ``yes''
	\ELSE
		\RETURN ``no''
	\ENDIF
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[H]
\caption{resolver(Entero $votantes$, Entero $candidatos$, Entero $candidato$, Matriz $votaciones$)}
\begin{algorithmic}[1]
	\STATE Matriz $prioridades$ $\leftarrow$ armarEleccion($votantes$, $candidatos$, $votaciones$)
	\STATE Digrafo $grafo$ $\leftarrow$ armarGrafo($votantes$, $candidatos$, $prioridades$)
	\STATE
	\RETURN recorrerGrafo($votantes$, $candidatos$, $candidato$, $grafo$)
\end{algorithmic}
\end{algorithm}

\subsection{An\'alisis de Complejidad}
Basicamente el algoritmo se divide en 3 etapas.

\begin{enumerate}
	\item Llenar la matriz de prioridades a partir de los datos de entrada.
	\item Construir el grafo a partir de la matriz de prioridades.
	\item Recorrer el grafo para ver si existe una solución (DFS).
\end{enumerate}

\subsubsection{Armar matriz de prioridades}
Para llenar la matriz de prioridades necesitamos recorrer todos los votantes y por cada uno de ellos
recorrer todos sus votos. Siendo $n$ la cantidad de candidatos y $m$ la de votantes nos quedar\'ia:

$$ \sum_{i=1}^{m} \sum_{j=1}^{n} O(1) \in O(n * m)$$


\subsubsection{Construir grafo}
Para construir el grafo dirigido que modela el problema necesitamos recorrer cada par de candidatos
que participan en la elección y por cada uno de ellos recorrer la lista de votantes y ver cual gana.
Para ver si un votante prefiere a un candidato o a otro solo basta con revisar la matriz de prioridades
y comparar los valores para la fila que corresponde a ese votante, lo que se hace en $O(1)$.
Por lo tanto, siendo $n$ la cantidad de candidatos y $m$ la de votantes nos quedar\'ia:

$$ \sum_{i=1}^{n} \sum_{j=i+1}^{n} \sum_{k=1}^{m} O(1) \in O(n^{2} * m)$$


\subsubsection{Recorrer el grafo (DFS)}
Para ver si el problema tiene solución recorremos el grafo usando DFS partiendo del nodo que representa al
candidato que queremos favorecer. Siendo $G = (V, E)$ el grafo dirigido que se debe recorrer, la complejidad del
algoritmo se puede dividir en tres partes:

\begin{enumerate}
	\item Crear el vector de nodos visitados e inicializarlo en 0 $\in O(|V|)$.
	\item Recorrer los nodos del grafo partiendo desde el candidato que se quiere que gane $\in O(|E|)$.
	\item Comprobar que todos los nodos fueron visitados  $\in O(|V|)$.
\end{enumerate}

Veamos en más detalle la complejidad de recorrer todos los nodos del grafo. Para recorrer todos los nodos usamos
una pila en donde vamos poniendo los nodos que se tienen que recorrer en las siguientes iteraciones.
Al principio se insertan en la pila todos los vecinos del candidato a favorecer, luego en cada iteración por cada
nodo no visitado se insertan en la pila todos sus vecinos. Por lo tanto en el peor caso el grafo es conexo y se
visitan todos los nodos, y por cada nodo se insertan todos sus vecinos, es decir todos a los nodos a los que les llega
una arista que sale desde él. Al final tendremos que ocurrieron tantas inserciones de nodos en la pila como aristas en el grafo
y por lo tanto la cantidad de iteraciones está dada por la cantidad de aristas que se tienen, entonces $\in O(|E|)$. \\

Resumiendo todo tenemos $O(|V| + |E| + |V|) \in O(|V| + |E|)$, y sabiendo que $|V| = n$ y que $|E| \leq |V|^{2}$ nos queda
$O(|V| + |E|) \in O(|V|^{2}) = O(n^{2})$.

\subsubsection{Conclusión}
Las 3 etapas del algoritmo tienen las siguientes complejidades:

\begin{enumerate}
	\item Armar la matriz de prioridades: $O( n * m )$.
	\item Construir el grafo: $O( n^{2} * m )$.
	\item Recorrer el grafo con DFS: $O( n^{2} )$.
\end{enumerate}

De modo que la complejidad del problema es $O( n * m + n^{2} * m + n^{2} ) = O(n^{2} * m )$.

\subsection{Casos patol\'ogicos de correctitud}
Se ha hecho un an\'alisis de diferentes casos, comprobando la correctitud del algoritmo frente a cada uno.

\subsubsection{Todos empatan}
Cuando todos los candidatos empatan el grafo no contiene ninguna arista y por lo tanto nig\'un candidato
estar\'ia en condiciones de ganar. Estos casos se encuentran en el archivo ``codigo/generadores/e3-correctitud-aislados.txt''.
%\newpage
\begin{figure}[h]
	\centering
	\renewcommand{\figurename}{Ejemplo}
	\caption[cap=Ejemplo]{Una elecci\'on con 5 candidatos y 2 votantes donde todos terminan empatados.}
	\subfloat[Votaciones] {
	\begin{tabular}{ c c c c c c }
		\textbf{Votante 1:} & 1 & 2 & 3 & 4 & 5 \\
		\textbf{Votante 2:} & 5 & 4 & 3 & 2 & 1 \\
	\end{tabular}
	}
	\hspace{12pt}
	\subfloat[Grafo] {
	\begin{tikzpicture}
		\SetVertexNormal[Shape = circle,
							FillColor  = white]
		%\SetVertexNoLabel
		\SetUpEdge[lw         = 1pt,
						color      = black,
						labelcolor = white,
						labeltext  = black,
						labelstyle = {sloped,draw,text=black}]
						
		\Vertex[x=1, y=2]{1}
		\Vertex[x=3, y=2]{2}
		\Vertex[x=0, y=0]{4}
		\Vertex[x=2, y=0]{3}
		\Vertex[x=4, y=0]{5}
	\end{tikzpicture}
	}
\end{figure}

\subsubsection{Candidato aislado}
Cuando alg\'un candidato empata con todos los dem\'as este queda representado como un nodo aislado, se ha an\'alizado este caso
tomando como el candidato a favorecer el que ha quedado aislado y tambi\'en tomando un candidato que pueda llegar a todos los
dem\'as excepto al aislado. En los dos casos el candidato favorecido no tiene posibilidades de ganar la elecci\'on.
Estos casos se encuentran en el archivo ``codigo/generadores/e3-correctitud-unoaislado.txt''.
\newpage
\begin{figure}[h]
	\centering
	\renewcommand{\figurename}{Ejemplo}
	\caption{Una elecci\'on con 5 candidatos y 2 votantes donde el nodo 5 ha quedado aislado y desde el nodo 1 se puede llegar todos los nodos menos al 5.}
	\subfloat[Votaciones] {
	\begin{tabular}{ c c c c c c }
		\textbf{Votante 1:} & 1 & 2 & 3 & 4 & 5 \\
		\textbf{Votante 2:} & 5 & 1 & 2 & 3 & 4 \\
	\end{tabular}
	}
	\hspace{12pt}
	\subfloat[Grafo] {
	\begin{tikzpicture}
		\SetVertexNormal[Shape = circle,
							FillColor  = white]
		%\SetVertexNoLabel
		\SetUpEdge[lw         = 1pt,
						color      = black,
						labelcolor = white,
						labeltext  = black,
						labelstyle = {sloped,draw,text=black}]
						
		\Vertex[x=1, y=2]{1}
		\Vertex[x=3, y=2]{5}
		\Vertex[x=0, y=0]{2}
		\Vertex[x=2, y=0]{3}
		\Vertex[x=4, y=0]{4}
		
		\tikzstyle{EdgeStyle}=[post, bend left]
		\Edges(1,3)
		\Edges(1,4)
		\Edges(2,3)
		\Edges(3,4)
		
		\tikzstyle{EdgeStyle}=[post, bend right]
		\Edges(1,2)
		\Edges(2,4)
	\end{tikzpicture}
	}
\end{figure}

\subsubsection{Ciclo}
En este caso las votaciones est\'an dadas de forma tal que entre todos los candidatos se forme un cilo y por lo tanto cualquier
candidato tiene posibilidades de ganar la elecci\'on. Estos casos se encuentran en el archivo ``codigo/generadores/e3-correctitud-ciclo.txt''.

\begin{figure}[h]
	\centering
	\renewcommand{\figurename}{Ejemplo}
	\caption{Una elecci\'on con 5 candidatos y 5 votantes donde se produce un ciclo entre todos los candidatos.}
	\subfloat[Votaciones] {
	\begin{tabular}{ c c c c c c }
		\textbf{Votante 1:} & 1 & 2 & 3 & 4 & 5 \\
		\textbf{Votante 2:} & 5 & 1 & 2 & 3 & 4 \\
		\textbf{Votante 1:} & 4 & 5 & 1 & 2 & 3 \\
		\textbf{Votante 1:} & 3 & 4 & 5 & 1 & 2 \\
		\textbf{Votante 1:} & 2 & 3 & 4 & 5 & 1 \\
	\end{tabular}
	}
	\hspace{12pt}
	\subfloat[Grafo] {
	\begin{tikzpicture}
		\SetVertexNormal[Shape = circle,
							FillColor  = white]
		%\SetVertexNoLabel
		\SetUpEdge[lw         = 1pt,
						color      = black,
						labelcolor = white,
						labeltext  = black,
						labelstyle = {sloped,draw,text=black}]
						
		\Vertex[x=1, y=2]{1}
		\Vertex[x=3, y=2]{5}
		\Vertex[x=0, y=0]{2}
		\Vertex[x=2, y=0]{3}
		\Vertex[x=4, y=0]{4}
		
		\tikzstyle{EdgeStyle}=[post, bend right]
		\Edges(1,2)
		\Edges(2,3)
		\Edges(3,4)
		\Edges(4,5)
		\Edges(5,1)
	\end{tikzpicture}
	}
\end{figure}
  

\subsection{Mediciones}
Dado que no existen ni mejores ni peores casos para el algoritmo ya que su complejidad est\'a dada por el tiempo
que toma construir el grafo a partir de la matriz de prioridades, $\Theta(n^{2} * m)$, se llevaron a cabo mediciones
solamente sobre un conjunto de casos aleatorios.

\input{problema3/aleatorio.tex}

\newpage
